//leetcode300. 最长递增子序列
//https://leetcode.cn/problems/longest-increasing-subsequence/
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
       //dp[i]以i结尾的最递增子序列的长度
       //1. 在区间[0, i - 1]取一个j，使得nums[j] < nums[i]
	   //   则此时dp[i] = dp[j] + 1，遍历[0, i - 1]可求得以i为结尾的递增子序列
	   //2. 若区间[0, i - 1]所有的nums[j] >= nums[i]
	   //   则此时dp[i] = 1
	   //所以dp[i] = max(dp[i], dp[j] + 1)
	   
		vector<int> dp(nums.size(), 1);
		int ans = 1;
	   for (int i = 0; i < nums.size(); ++i)
	   {
		   for (int j = 0; j < i; ++j)
		   {
			   //遍历全部符合nums[j] < nums[i]
				if (nums[j] < nums[i]) 
					dp[i] = max(dp[i], dp[j] + 1);
			   //取最大值
				if (ans < dp[i])
					ans = dp[i];
		   }
	   } 

       return ans;
    }
};